Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (95,941094)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 95 | |||
Set to 0 | 0 | Set to 1 | 1 | 941094 | Quotient of 95/941094 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 95/941094 | 95 | Quotient of 941094/95 | 9906 |
0 - (9906 x 1) | -9906 | 1 - (9906 x 0) | 1 | Remainder of 941094/95 | 24 | Quotient of 95/24 | 3 |
1 - (3 x -9906) | 29719 | 0 - (3 x 1) | -3 | Remainder of 95/24 | 23 | Quotient of 24/23 | 1 |
-9906 - (1 x 29719) | -39625 | 1 - (1 x -3) | 4 | Remainder of 24/23 | 1 | Quotient of 23/1 | 23 |
29719 - (23 x -39625) | 941094 | -3 - (23 x 4) | -95 | Remainder of 23/1 | 0 | Quotient of 1/0 | 0 |
a = -39625 and b = 4
ax + by = gcd(a,b)
95x + 941094y = gcd(95